package com.example.leetcode.linklist;


import java.util.LinkedHashMap;
import java.util.Map;

/**
 * 请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
 * 实现 LRUCache 类：
 * LRUCache(int capacity) 以正整数作为容量capacity初始化LRU缓存
 * int get(int key) 如果关键字key存在于缓存中，则返回关键字的值，否则返回-1 。
 * void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
 * 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
 */
public class LRUCache {
    public static void main(String[] args) {

    }

    private Integer capacity;
    private Map<Integer, Integer> cache = new LinkedHashMap<>();

    public LRUCache(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        // 缓存用过就刷为最经常用
        Integer i = cache.get(key);
        makeRecent(key);
        return i;
    }

    public void put(int key, int value) {
        // 已经包含的，更新，使之为最新
        if (cache.containsKey(key)) {
            cache.put(key,value);
            makeRecent(key);
            return;
        }

        // 缓存满了，去除最不经常用的
        if (cache.size() >= capacity) {
            Integer next = cache.keySet().iterator().next();
            cache.remove(next);
        }

        cache.put(key,value);
    }


    /**
     * 是缓存变为最新
     */
    private void makeRecent(Integer key) {
        Integer value = cache.get(key);
        cache.remove(key);
        cache.put(key, value);
    }

}
